package com.lsa.cormen.ch15.samples;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.AdjGraph;
import com.lsa.helpers.graph.IGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class Knapsack {
    static class NodeData{
        int node;
        int itemLevel; // corresponds to the item considered
        int weight;  // weight so far
        
        double value; // value so far - will be determined by the DAG-shortest-path
        int parent; //will be determined by the DAG-shortest-path
        boolean isTake; // toTake || !toTake - will be set by DAG-shortest-path
        
        Object attr;
        
        NodeData(int node, int itemLevel, int weight, double value) {
            this.node = node;
            this.itemLevel = itemLevel;
            this.weight = weight;
            this.value = value;
        }

        NodeData(int itemLevel, int weight, double value) {
            this.itemLevel = itemLevel;
            this.weight = weight;
            this.value = value;
        }
    }
    
    public static Integer[] knapsackByShortestPath(int capacity, int[] weights, double[] values) {
        IGraph<NodeData, Double> graph = new AdjGraph<NodeData, Double>(true, 0);
        List<NodeData> finalStates = new ArrayList<NodeData>();
        
        buildProblemGraph(graph, capacity, weights, values, finalStates);
        dagShortestPath(graph);
        
        NodeData node = Collections.min(finalStates, new Comparator<NodeData>() {
            @Override
            public int compare(NodeData n1, NodeData n2) {
                double result = n1.value - n2.value;
                if (result > 0) {
                    return 1;
                }
                else if (result < 0) {
                    return -1;
                }
                else {
                    return 0;
                }
            }
        });
        
        LinkedList<Integer> taken = new LinkedList<Integer>();
        
        do{
            if (node.isTake) {
                taken.addFirst(node.itemLevel-1);
            }
            node = graph.nodeAttr(node.parent);
        }
        while(node.itemLevel > 0);
        
        try {
            TgfGraphFactory.saveGraphAsTgf(graph, new IConverter<NodeData, String>() {
                @Override
                public String convert(NodeData data) {
                    return String.format("l=%s,w=%s,t=%s", data.itemLevel, data.weight, data.isTake);
                }
            }, new IConverter<Double, String>() {

                @Override
                public String convert(Double data) {
                    return ""+data;
                }
            }, "data/gen/cormen/ch15/knapsack.tgf");
        } catch (IOException e) {
            System.out.println(e);
        }
        
        return taken.toArray(new Integer[0]);
    }

    public static void dagShortestPath(IGraph<NodeData, Double> graph) {
        Deque<NodeData> topSorted = new LinkedList<NodeData>();
        topSort(graph, 0, topSorted);
        
        for (NodeData attrFrom : topSorted) {
            int u = attrFrom.node;
            List<Integer> adj = graph.adjacencyList(u);
            for (Integer v : adj) {
                NodeData attrTo = graph.nodeAttr(v);
                Double w = graph.edgeAttr(u, v);
                if (attrTo.value > attrFrom.value + w) {
                    attrTo.value = attrFrom.value + w;
                    if (w != 0) {
                        attrTo.isTake = true;
                    }
                    else {
                        attrTo.isTake = false;
                    }
                    attrTo.parent = u;
                }
            }
        }
    }

    public static void buildProblemGraph(IGraph<NodeData, Double> graph,
            int capacity, int[] weights, double[] values, 
            List<NodeData> finalStates) {
        int n = weights.length; // item count
        
        NodeData startNodeData = new NodeData(0, -1, 0, 0);
        graph.addNode(startNodeData);
        
        NodeData nodeDate = new NodeData(1, 0, 0, 0); // (0,0) node
        graph.addNode(nodeDate);
        graph.addEdge(0, 1, 0.0);
        
        Queue<NodeData> buildGraphQueue = new LinkedList<NodeData>();
        buildGraphQueue.add(nodeDate);
        
        /**
         * Class to store NodeData in the HT for the purpose of the reuse
         * @author lsa
         */
        class NodeDataKey{
            int itemLevel;
            int weight;
            
            NodeDataKey(int itemLevel, int weight) {
                this.itemLevel = itemLevel;
                this.weight = weight;
            }
            
            @Override
            public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + itemLevel;
                result = prime * result + weight;
                return result;
            }
            @Override
            public boolean equals(Object obj) {
                if (this == obj)
                    return true;
                if (obj == null)
                    return false;
                if (getClass() != obj.getClass())
                    return false;
                NodeDataKey other = (NodeDataKey) obj;
                if (itemLevel != other.itemLevel)
                    return false;
                if (weight != other.weight)
                    return false;
                return true;
            }
        }
        Map<NodeDataKey, NodeData> key2State = new HashMap<NodeDataKey, NodeData>();
        
        while(!buildGraphQueue.isEmpty()) {
            nodeDate = buildGraphQueue.poll();
            int u = nodeDate.node;
            
            if (nodeDate.itemLevel == n) {
                finalStates.add(nodeDate);
                continue;
            }
            
            int nextItemLevel = nodeDate.itemLevel + 1;
            // 'not take' node
            int nextItemWeight = nodeDate.weight; 
            
            NodeDataKey key = new NodeDataKey(nextItemLevel, nextItemWeight);
            NodeData nextNodeData = key2State.get(key);
            int v1;
            if (nextNodeData == null) {
                nextNodeData = new NodeData(nextItemLevel, nextItemWeight, 0);
                v1 = graph.addNode(nextNodeData);
                key2State.put(key, nextNodeData);
                nextNodeData.node = v1;
                buildGraphQueue.add(nextNodeData);
            }
            else {
                v1 = nextNodeData.node;
            }
            
            graph.addEdge(u, v1, 0.0);
            
            // 'take' node
            nextItemWeight = nodeDate.weight + weights[nodeDate.itemLevel];
            if (nextItemWeight <= capacity) {
                key = new NodeDataKey(nextItemLevel, nextItemWeight);
                nextNodeData = key2State.get(key);
                int v2;
                if (nextNodeData == null) {
                    nextNodeData = new NodeData(nextItemLevel, nextItemWeight, 0);
                    v2 = graph.addNode(nextNodeData);
                    nextNodeData.node = v2;
                    buildGraphQueue.add(nextNodeData);
                }
                else {
                    v2 = nextNodeData.node;
                }
                
                graph.addEdge(u, v2, -values[nodeDate.itemLevel]);
            }
        }
    }
    
    private static void topSort(IGraph<NodeData, Double> g, int u,
            Deque<NodeData> topSorted) {
        g.nodeAttr(u).attr = Boolean.TRUE; // discovered
        List<Integer> adj = g.adjacencyList(u);
        for (Integer v : adj) {
            if (g.nodeAttr(v).attr == null) { // not discovered
                topSort(g, v, topSorted);
            }
        }
        topSorted.addFirst(g.nodeAttr(u));
    }

    public static Integer[] knapsackByDp(int capacity, int[] weights, double[] values) {
        class DP{
            int parent = -1;
            double maxValue;
            boolean isTake; // toTake || !toTake 
        }
        int n = weights.length; // item count
        
        /*
         * dp[i][j] is the maximum value that can be obtained by using a subset of the items i . . . n - 1 (last
         * n - i items) which weighs at most j pounds
         * */
        DP[][] dp = new DP[n + 1][capacity + 1];
        for (int j = 0; j <= capacity; j++) {
            dp[n][j] = new DP();
            dp[n][j].maxValue = 0;
        }
        for (int i = n - 1; i > -1; i--) {
            for (int j = 0; j <= capacity; j++) {
                dp[i][j] = new DP();
                dp[i][j].maxValue = dp[i+1][j].maxValue;
                dp[i][j].parent = j;
                
                if (j >= weights[i] ) {
                    int takeDecisionParent = j - weights[i];
                    double takeDecisionValue = dp[i+1][takeDecisionParent].maxValue + values[i];
                    if (dp[i][j].maxValue < takeDecisionValue) {
                        dp[i][j].isTake = true;
                        dp[i][j].maxValue = takeDecisionValue;
                        dp[i][j].parent = takeDecisionParent;
                    }
                }
            }
        }
        
        List<Integer> taken = new ArrayList<Integer>();
        
        int j = capacity;
        int i = 0;
        do{
            if (dp[i][j].isTake) {
                taken.add(i);
            }
            j = dp[i][j].parent;
            i++;
        }
        while(i <= n);
        return taken.toArray(new Integer[0]);
    }
}
